package toOffer;

/**
 * @author YuanAo
 * @date 2024/9/30 14:02
 * @description 二叉树剪枝
 */

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * 给定一个二叉树 根节点 root ，树的每个节点的值要么是 0，要么是 1。请剪除该二叉树中所有节点的值为 0 的子树。
 *
 * 节点 node 的子树为 node 本身，以及所有 node 的后代。
 *
 * 输入: [1,null,0,0,1] 输出: [1,null,0,null,1]
 *
 * 输入: [1,0,1,0,0,0,1] 输出: [1,null,1,null,1]
 *
 * 输入: [1,1,0,1,1,0,1,0] 输出: [1,1,0,1,1,null,1]
 */
public class toOffer47 {
    public static void main(String[] args) {
        TreeNode node1 = new TreeNode(0);
        TreeNode node2 = new TreeNode(1);
        TreeNode rNode = new TreeNode(0, node1, node2);
        TreeNode lNode = new TreeNode(0, null, null);
        TreeNode treeNode = new TreeNode(1, lNode, rNode);
        fun(treeNode);
//        TreeNode tree = pruneTree(treeNode);
//        fun(tree);
    }

    public static void fun(TreeNode tree){
        ArrayList<TreeNode> nodeLists = new ArrayList<>();
        List<Integer> list = sequenceTraversal(tree);
        for (Integer i : list) {
            System.out.print(i + " ");
        }
    }

    public static List<Integer> sequenceTraversal(TreeNode treeNode){
        LinkedList<TreeNode> queue = new LinkedList<>();
        if (treeNode != null){
            queue.offer(treeNode);
        }
        ArrayList<Integer> list = new ArrayList<>();
        while (!queue.isEmpty()){
            TreeNode node = queue.poll();
            list.add(node.val);
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
        return list;
    }

    /**
     * 需要减去的节点，分两种情况：
     * （1）节点是叶节点，它的值为0
     * （2）节点不是叶节点，它的子节点包含自己本身的值全都为0
     * @param root
     * @return
     */
    public static TreeNode pruneTree(TreeNode root) {
        if (root == null){
            return root;
        }
        pruneTree(root.left);
        pruneTree(root.right);
        if (root.left == null && root.right == null && root.val == 0){
            return null;
        }
        return root;
    }

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

}
